//
// Created by Luhang on 2023/5/16/016.
//

#ifndef INC_0406_BSTREE_H
#define INC_0406_BSTREE_H

#endif //INC_0406_BSTREE_H

#include <iostream>
using namespace std;

namespace Key {
    template<class K>
    struct BSTreeNode {
        BSTreeNode<K> *_left;
        BSTreeNode<K> *_right;
        K _key;

        BSTreeNode(const K &key)
                : _left(nullptr)
                , _right(nullptr)
                , _key(key) {
        }
    };

    template<class K>
    class BSTree {
        typedef BSTreeNode<K> Node;
    public:
        BSTree() = default; // 强制生成默认构造

        BSTree(const BSTree<K> &t) {
            _root = Copy(t._root);
        }

        BSTree<K> &operator=(BSTree<K> t) {
            swap(_root, t._root);
            return *this;
        }

        ~BSTree() {
            Destroy(_root);
            //_root = nullptr;
        }

        Node *Find(const K &key) {
            Node *cur = _root;
            while (cur) {
                if (cur->_key < key)
                    cur = cur->_right;
                else if (cur->_key > key)
                    cur = cur->_left;
                else
                    return cur;
            }
            return nullptr;
        }

        bool Insert(const K &key) {
            if (_root == nullptr) {
                _root = new Node(key);
                return true;
            }
            Node *cur = _root;
            Node *parent = nullptr;
            while (cur) {
                if (cur->_key < key) {
                    parent = cur;
                    cur = cur->_right;
                } else if (cur->_key > key) {
                    parent = cur;
                    cur = cur->_left;
                } else
                    return false;
            }
            cur = new Node(key);
            if (parent->_key < key)
                parent->_right = cur;
            else
                parent->_left = cur;
            return true;
        }

        bool Erase(const K &key) {
            Node *parent = nullptr;
            Node *cur = _root;
            while (cur) {
                if (cur->_key < key) {
                    parent = cur;
                    cur = cur->_right;
                } else if (cur->_key > key) {
                    parent = cur;
                    cur = cur->_left;
                } else {
                    //找到Key,开始删除
                    //1.左为空
                    if (cur->_left == nullptr) {
                        if (cur == _root)
                            _root = cur->_right;
                        else {
                            if (parent->_left == cur)
                                parent->_left = cur->_right;
                            else
                                parent->_right = cur->_right;
                        }
                        delete cur;
                    }
                        //2.右为空
                    else if (cur->_right == nullptr) {
                        if (cur == _root)
                            _root = cur->_left;
                        else {
                            if (parent->_left == cur)
                                parent->_left = cur->_left;
                            else
                                parent->_right = cur->_left;
                        }
                        delete cur;
                    }
                        //左右均不为空
                        //需找右树最小节点（最左节点）或左树最大节点（最右节点）替代
                    else {
                        Node *pMinRight = cur;
                        Node *MinRight = cur->_right;
                        while (MinRight->_left) {
                            pMinRight = MinRight;
                            MinRight = MinRight->_left;
                        }
                        cur->_key = MinRight->_key;
                        if (pMinRight->_right == MinRight)
                            pMinRight->_right = MinRight->_right;
                        else
                            pMinRight->_left = MinRight->_right;
                        delete MinRight;
                    }
                    return true;
                }
            }
            return false;
        }

        bool FindR(const K &key) {
            return _FindR(_root, key);
        }

        bool InsertR(const K &key) {
            return _InsertR(_root, key);
        }

        bool EraseR(const K &key) {
            return _EraseR(_root, key);
        }

        //成员函数递归都嵌套一层函数
        void InOrder() {
            _InOrder(_root);
            cout << endl;
        }

    protected:
        Node *Copy(Node *root) {
            if (root == nullptr)
                return nullptr;
            Node *newRoot = new Node(root->_key);
            newRoot->_left = Copy(root->_left);
            newRoot->_right = Copy(root->_right);
            return newRoot;
        }

        void Destroy(Node *&root) {
            if (root == nullptr)
                return;

            Destroy(root->_left);
            Destroy(root->_right);

            delete root;
            root = nullptr;
        }

        bool _FindR(Node *root, const K &key) {
            if (root == nullptr)
                return false;
            if (root->_key == key)
                return true;
            if (root->_key < key)
                return _FindR(root->_right, key);
            else
                return _FindR(root->_left, key);
        }

        bool _InsertR(Node *&root, const K &key) {
            if (root == nullptr) {
                root = new Node(key);
                return true;
            }
            if (root->_key < key)
                return _InsertR(root->_right, key);
            else if (root->_key > key)
                return _InsertR(root->_left, key);
            else
                return false;
        }

        bool _EraseR(Node *&root, const K &key) {
            if (root == nullptr)
                return false;
            if (root->_key < key)
                return _EraseR(root->_right, key);
            else if (root->_key > key)
                return _EraseR(root->_left, key);
            else {
                Node *del = root;
                if (root->_right == nullptr)
                    root = root->_left;
                else if (root->_left == nullptr)
                    root = root->_right;
                else {
                    Node *maxLeft = root->_left;
                    while (maxLeft->_right) {
                        maxLeft = maxLeft->_right;
                    }
                    swap(root->_key, maxLeft->_key);
                    //递归到子树继续删除
                    //不能传maxLeft，因为其为局部变量，没法用引用
                    return _EraseR(root->_left, key);
                }
                delete del;
                return true;
            }
        }

        //不能给缺省值_root，因为1.缺省值必须为常量或全局，2.访问成员变量需要this
        void _InOrder(Node *root) {
            if (root == nullptr)
                return;
            _InOrder(root->_left);
            cout << root->_key << " ";
            _InOrder(root->_right);
        }

    private:
        Node *_root = nullptr;
    };
}

namespace Key_value {
    template<class K, class V>
    struct BSTreeNode {
        BSTreeNode<K, V> *_left;
        BSTreeNode<K, V> *_right;
        K _key;
        V _value;

        BSTreeNode(const K &key, const V& value)
                : _left(nullptr)
                , _right(nullptr)
                , _key(key)
                ,_value(value){
        }
    };

    template<class K, class V>
    class BSTree {
        typedef BSTreeNode<K, V> Node;
    public:
        BSTree() = default; // 制定强制生成默认构造

        BSTree(const BSTree<K, V> &t) {
            _root = Copy(t._root);
        }

        BSTree<K, V> &operator=(BSTree<K, V> t) {
            swap(_root, t._root);
            return *this;
        }

        ~BSTree() {
            Destroy(_root);
            //_root = nullptr;
        }

        Node* Find(const K &key) {
            Node *cur = _root;
            while (cur) {
                if (cur->_key < key)
                    cur = cur->_right;
                else if (cur->_key > key)
                    cur = cur->_left;
                else
                    return cur;
            }
            return nullptr;
        }

        bool Insert(const K &key, const V& value) {
            if (_root == nullptr) {
                _root = new Node(key, value);
                return true;
            }
            Node *cur = _root;
            Node *parent = nullptr;
            while (cur) {
                if (cur->_key < key) {
                    parent = cur;
                    cur = cur->_right;
                } else if (cur->_key > key) {
                    parent = cur;
                    cur = cur->_left;
                } else
                    return false;
            }
            cur = new Node(key, value);
            if (parent->_key < key)
                parent->_right = cur;
            else
                parent->_left = cur;
            return true;
        }

        bool Erase(const K &key) {
            Node *parent = nullptr;
            Node *cur = _root;
            while (cur) {
                if (cur->_key < key) {
                    parent = cur;
                    cur = cur->_right;
                } else if (cur->_key > key) {
                    parent = cur;
                    cur = cur->_left;
                } else {
                    //找到Key,开始删除
                    //1.左为空
                    if (cur->_left == nullptr) {
                        if (cur == _root)
                            _root = cur->_right;
                        else {
                            if (parent->_left == cur)
                                parent->_left = cur->_right;
                            else
                                parent->_right = cur->_right;
                        }
                        delete cur;
                    }
                        //2.右为空
                    else if (cur->_right == nullptr) {
                        if (cur == _root)
                            _root = cur->_left;
                        else {
                            if (parent->_left == cur)
                                parent->_left = cur->_left;
                            else
                                parent->_right = cur->_left;
                        }
                        delete cur;
                    }
                        //左右均不为空
                        //需找右树最小节点（最左节点）或左树最大节点（最右节点）替代
                    else {
                        Node *pMinRight = cur;
                        Node *MinRight = cur->_right;
                        while (MinRight->_left) {
                            pMinRight = MinRight;
                            MinRight = MinRight->_left;
                        }
                        cur->_key = MinRight->_key;
                        if (pMinRight->_right == MinRight)
                            pMinRight->_right = MinRight->_right;
                        else
                            pMinRight->_left = MinRight->_right;
                        delete MinRight;
                    }
                    return true;
                }
            }
            return false;
        }

        //成员函数递归都嵌套一层函数
        void InOrder() {
            _InOrder(_root);
            cout << endl;
        }

    protected:
        Node *Copy(Node *root) {
            if (root == nullptr)
                return nullptr;
            Node *newRoot = new Node(root->_key, root->_value);
            newRoot->_left = Copy(root->_left);
            newRoot->_right = Copy(root->_right);
            return newRoot;
        }

        void Destroy(Node *&root) {
            if (root == nullptr)
                return;

            Destroy(root->_left);
            Destroy(root->_right);

            delete root;
            root = nullptr;
        }

        //不能给缺省值_root，因为1.缺省值必须为常量或全局，2.访问成员变量需要this
        void _InOrder(Node *root) {
            if (root == nullptr)
                return;
            _InOrder(root->_left);
            cout << root->_key << ":" << root->_value << endl;
            _InOrder(root->_right);
        }

    private:
        Node *_root = nullptr;
    };
}